import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Solution1129 {
    public int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
        int[] ansR=new int[n];
        Arrays.fill(ansR,-1);
        ansR[0]=0;
        int[] ansB=new int[n];
        Arrays.fill(ansB,-1);
        int[] first=new int[n];
        Arrays.fill(first,-1);
        int[] next=new int[redEdges.length+blueEdges.length];
        int[] go=new int[next.length];
        int[] type=new int[next.length];
        int count=0;
        for (int[] redEdge : redEdges) {
            next[count]=first[redEdge[0]];
            first[redEdge[0]]=count;
            go[count]=redEdge[1];
            type[count]=0;
            count++;
        }
        for (int[] blueEdge : blueEdges) {
            next[count]=first[blueEdge[0]];
            first[blueEdge[0]]=count;
            go[count]=blueEdge[1];
            type[count]=1;
            count++;
        }
        Queue<Integer> queue=new LinkedList<>();
        queue.offer(0);
        while (!queue.isEmpty()){
            int p=queue.poll();
            int v=first[p];
            while (v!=-1){
                int k=go[v];
                if (ansR[p]!=-1 && (type[v]+ansR[p])%2==0 && (ansB[k]==-1 || ansB[k]>ansR[p]+1)){
                    ansB[k]=ansR[p]+1;
                    queue.offer(k);
                }
                if (ansB[p]!=-1 && (type[v]+ansB[p])%2==0 && (ansR[k]==-1 || ansR[k]>ansB[p]+1)){
                    ansR[k]=ansB[p]+1;
                    queue.offer(k);
                }
                v=next[v];
            }
        }
        int[] ans=new int[n];
        for (int i=0;i<n;i++){
            if (ansR[i]==-1){
                ans[i]=ansB[i];
            }else{
                if (ansB[i]==-1){
                    ans[i]=ansR[i];
                }else {
                    ans[i]=Math.min(ansR[i],ansB[i]);
                }
            }
        }
        Arrays.fill(ansR,-1);
        Arrays.fill(ansB,-1);
        ansB[0]=0;
        queue.offer(0);
        while (!queue.isEmpty()){
            int p=queue.poll();
            int v=first[p];
            while (v!=-1){
                int k=go[v];
                if (ansR[p]!=-1 && (type[v]+ansR[p])%2==1 && (ansB[k]==-1 || ansB[k]>ansR[p]+1)){
                    ansB[k]=ansR[p]+1;
                    queue.offer(k);
                }
                if (ansB[p]!=-1 && (type[v]+ansB[p])%2==1 && (ansR[k]==-1 || ansR[k]>ansB[p]+1)){
                    ansR[k]=ansB[p]+1;
                    queue.offer(k);
                }
                v=next[v];
            }
        }
        for (int i=0;i<n;i++){
            if (ans[i]==-1){
                if (ansR[i]==-1){
                    ans[i]=ansB[i];
                }else{
                    if (ansB[i]==-1){
                        ans[i]=ansR[i];
                    }else {
                        ans[i]=Math.min(ansR[i],ansB[i]);
                    }
                }
            }else{
                if (ansR[i]!=-1){
                    ans[i]=Math.min(ans[i],ansR[i]);
                }
                if (ansB[i]!=-1){
                    ans[i]=Math.min(ans[i],ansB[i]);
                }
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new Solution1129().shortestAlternatingPaths(5, new int[][]{{3,2}, {4,1},{1,4},{2,4}}, new int[][]{{2,3},{0,4},{4,3},{4,4},{4,0},{1,0}})));
    }
}
